|
In mathematics, economics and computer science, particularly in the fields of combinatorics, game theory and algorithms, the stable-roommate problem (SRP) is the problem of finding a stable matching—a matching in which there is no pair of elements where ''both'' members prefer their partner in a different matching over their partner in the stable matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of “men” and “women”. It is commonly stated as: : In a given instance of the stable-roommates problem (SRP), each of ''2n'' participants ranks the others in strict order of preference. A matching is a set of ''n'' disjoint pairs of participants. A matching ''M'' in an instance of SRP is stable if there are no two participants ''x'' and ''y'', each of whom prefers the other to their partner in ''M''. Such a pair is said to block ''M'', or to be a blocking pair with respect to ''M''. ==Solution== Unlike the stable marriage problem, a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal example of a stable pairing not existing, consider 4 people A, B, C, and D, whose rankings are: : A:(B,C,D), B:(C,A,D), C:(A,B,D), D:(A,B,C) In this ranking, each of A, B, and C is the most preferable person for someone. In any solution, one of A, B, or C ''must'' be paired with D and the other two with each other (for example AD and BC), yet for anyone who is partnered with D, another member will have rated them highest, and D’s partner will in turn prefer this other member over D. In this example, AC is a more favorable pairing than AD, but the necessary remaining pairing of BD then raises the same issue, illustrating the absence of a stable matching for these participants and their preferences. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Stable roommates problem」の詳細全文を読む スポンサード リンク
|